package leetcode_jz_offer.day1;

/**
 * 用两个栈实现队列
 **/


import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 用两个栈实现一个队列(leetcode232也是这种题)
 * 队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead
 * 分别完成在队列尾部插入整数和在队列头部删除整数的功能。
 * (若队列中没有元素，deleteHead操作返回 -1 )
 */

/**
 * 思路：一个栈输入，一个栈输出
 * 1.输入栈输入内容即尾插内容
 * 2.将输入栈内容弹到输出栈中，此时输出栈栈顶元素就是最开始输入的元素，弹出即进行了队列的头删
 */
public class Num9_StackToQueue {
    Stack<Integer> input;
    Stack<Integer> output;
    public Num9_StackToQueue() {
        //构造方法初始化
        input=new Stack<>();
        output=new Stack<>();
    }
//    Deque<Integer> input;
//    Deque<Integer> output;
//    public Num9_StackToQueue() {
//        //构造方法初始化
//        input=new ArrayDeque<>();
//        output=new ArrayDeque<>();
//    }

    //队列尾部插入整数
    public void appendTail(int value) {
        input.push(value);//向栈中插入元素
    }
    //队列头部删除整数：将输入栈中的元素弹出到另一个栈（输出栈），此时栈顶元素就是需要删除的元素
    public int deleteHead() {
        //判断是否为空
        if(output.isEmpty()){
            if(input.isEmpty()){
                //两个栈都为空时没有元素可以弹出
                return -1;
            }
            //output为空则不断将input的所有元素加到output中
            while (!input.isEmpty()){
                output.push(input.pop());
            }
            //此时input为空，元素全部到了output栈中,弹出栈顶元素，即删除了队列头部元素
        }
        return output.pop();
    }
}
